package leetcode_801_900;

import java.util.*;

public class LeeCode_874 {
    public static void main(String[] args) {
//        System.out.println(robotSim(new int[]{4, -1, 3}, new int[][]{}));
//        System.out.println(robotSim(new int[]{4, -1, 4, -2, 4}, new int[][]{{2,4}}));
//        System.out.println(robotSim(new int[]{-2,-1,8,9,6}, new int[][]{{0, 1}}));
//        System.out.println(robotSim(new int[]{4, -1, 4, -2, 4}, new int[][]{{2, 4}}));
//        System.out.println(robotSim(new int[]{7,-2,-2,7,5},
//                new int[][]{{-3,2},{-2,1},{0,1},{-2,4},{-1,0},{-2,-3},{0,-3},{4,4},{-3,3},{2,2}}));

        System.out.println(robotSim(new int[]{-2,-1,-2,3,7},
                new int[][]{{1,-3},{2,-3},{4,0},{-2,5},{-5,2},{0,0},{4,-4},{-2,-5},{-1,-2},{0,2}}));
    }
    private static int robotSim(int[] commands, int[][] obstacles) {
        Map<Integer, List<Integer>> xty = new HashMap<>();
        Map<Integer, List<Integer>> ytx = new HashMap<>();
        for (int[] obstacle : obstacles) {
            int x = obstacle[0];
            int y = obstacle[1];
            if (xty.containsKey(x)){
                xty.get(x).add(y);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(y);
                xty.put(x, list);
            }
            if (ytx.containsKey(y)){
                ytx.get(y).add(x);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(x);
                ytx.put(y, list);
            }
        }
        for (Integer key : xty.keySet()) {
            xty.get(key).sort(Comparator.comparingInt(o -> o));
        }
        for (Integer key : ytx.keySet()) {
            ytx.get(key).sort(Comparator.comparingInt(o -> o));
        }
        int dirN = 40000, x = 0, y = 0;
        int ans = 0;
        for (int command : commands) {
            if (command == -2){
                dirN--;
            }else if (command == -1){
                dirN++;
            }else {
                int dir = dirN % 4;
                switch (dir){
                    case 0 :{
                        int goal = y + command;
                        if (!xty.containsKey(x)){
                            y = goal;
                        }else {
                            List<Integer> list = xty.get(x);
                            int biggerI = searchBigger(list, y);
                            int bigger = -1;
                            if (biggerI != -1){
                                bigger = list.get(biggerI);
                            }
                            if (biggerI == -1){
                                y = goal;
                            }else if (goal >= bigger){
                                y = bigger - 1;
                            }else {
                                y = goal;
                            }
                        }
                        break;
                    }
                    case 1:{
                        int goal = x + command;
                        if (!ytx.containsKey(y)){
                            x = goal;
                        }else {
                            List<Integer> list = ytx.get(y);
                            int biggerI = searchBigger(list, x);
                            int bigger = -1;
                            if (biggerI != -1){
                                bigger = list.get(biggerI);
                            }
                            if (biggerI == -1){
                                x = goal;
                            }else if (goal >= bigger){
                                x = bigger - 1;
                            }else {
                                x = goal;
                            }
                        }
                        break;
                    }
                    case 2:{
                        int goal = y - command;
                        if (!xty.containsKey(x)){
                            y = goal;
                        }else {
                            List<Integer> list = xty.get(x);
                            int smallerI = searchSmaller(list, y);
                            int smaller = -1;
                            if (smallerI != -1){
                                smaller = list.get(smallerI);
                            }
                            if (smallerI == -1){
                                y = goal;
                            }else if (goal <= smaller){
                                y = smaller + 1;
                            }else {
                                y = goal;
                            }
                        }
                        break;
                    }
                    case 3:{
                        int goal = x - command;
                        if (!ytx.containsKey(y)){
                            x = goal;
                        }else {
                            List<Integer> list = ytx.get(y);
                            int smallerI = searchSmaller(list, x);
                            int smaller = -1;
                            if (smallerI != -1){
                                smaller = list.get(smallerI);
                            }
                            if (smallerI == -1){
                                x = goal;
                            }else if (goal <= smaller){
                                x = smaller + 1;
                            }else {
                                x = goal;
                            }
                        }
                        break;
                    }
                }
                ans = Math.max(ans, x * x + y * y);
            }
        }
        return ans;
    }
    private static int searchSmaller(List<Integer> list, int goal){
        int l = 0, r = list.size() - 1;
        while (l < r){
            int m = (l + r + 1) / 2;
            if (list.get(m) > goal){
                r = m - 1;
            }else {
                l = m;
            }
        }
        if (list.get(l) >= goal){
            return -1;
        }
        return l;
    }
    private static int searchBigger(List<Integer> list, int goal){
        int l = 0, r = list.size() - 1;
        while (l < r){
            int m = (l + r) / 2;
            if (list.get(m) < goal){
                l = m + 1;
            }else {
                r = m;
            }
        }
        if (list.get(l) <= goal){
            return -1;
        }
        return l;
    }
}
